package com.learn.algorithm_141;

import com.dataconsruct.ListNode;
import org.junit.Test;

import java.util.HashSet;
import java.util.Set;

/**
 * 判断是否是环形链表
 * https://leetcode-cn.com/problems/linked-list-cycle/
 *
 * @author gatts, 2022/2/7 11:00
 */
public class CycleListNode {

    @Test
    public void test() {
        ListNode head = new ListNode(3);
        ListNode first = new ListNode(2);
        ListNode second = new ListNode(0);
        ListNode third = new ListNode(-4);

        head.next = first;
        first.next = second;
        second.next = third;
        third.next = first;

        System.out.println(hasCycle(head));
    }

    /**
     * 快慢指针，快指针每次移动两步，慢指针每次一步
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        ListNode slow, fast;
        if ((slow = head) == null || (fast = head.next) == null) {
            return false;
        }
        while (slow != fast) {
            // 龟兔赛跑开始，非环形链表必然会有终点为null
            // 对快指针判空即可
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        // 环形链表必然出现快慢指针是相同节点的时刻
        return true;
    }

    /**
     * hash方式
     * @param head
     * @return
     */
    public boolean hasCycle0(ListNode head) {
        Set<ListNode> seen = new HashSet<>();
        while (head != null) {
            if (!seen.add(head)) {
                return true;
            }
            head = head.next;
        }
        return false;
    }

}
